package stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostfixExpression {
    public static void main(String[] args) {
        String infixExpression = "29*(3+5)-4/2";
        System.out.println(expressionList(infixExpression));
        System.out.println(infixToPostfix(expressionList(infixExpression)));
    }

    private static List<String> infixToPostfix(List<String> infixExpression) {
        Stack<String> operatorStack = new Stack<>();
        List<String> list = new ArrayList<>();
        int index = 0;
        for (String item : infixExpression) {
            if (isNum(item)) { // 数字
                list.add(item);
            } else if (isOperator(item)){ // 符号
                if (operatorStack.isEmpty() || operatorStack.peek().equals("(") || priority(item) > priority(operatorStack.peek())) {
                    operatorStack.push(item);
                }  else {
                    while (!operatorStack.isEmpty() && priority(item) <= priority(operatorStack.peek())) {
                        list.add(operatorStack.pop());
                    }
                    operatorStack.push(item);
                }
            } else { // 括号
                if (item.equals("(")) {
                    operatorStack.push(item);
                } else {
                    while (!operatorStack.peek().equals("(")){
                        list.add(operatorStack.pop());
                    }
                    operatorStack.pop();
                }
            }
        }
        while (!operatorStack.isEmpty()) {
            list.add(operatorStack.pop());
        }
        return list;
    }

    private static List<String> expressionList(String expression) {
        List<String> list = new ArrayList<>();
        int size = expression.length();
        String keepNum = "";
        for (int i = 0; i < size; i++) {
            String c = expression.substring(i, i+1);
            if (!isNum(c)) {
                list.add(c);
            } else {
                if (i == size - 1 || !isNum(expression.substring(i+1, i+2))) {
                    list.add(keepNum + c);
                    keepNum = "";
                } else {
                    keepNum = keepNum + c;
                }
            }
        }
        return list;
    }

    private static boolean isNum(String str) {
        return str.matches("\\d+");
    }

    private static boolean isOperator(String c) {
        return c.equals("+") || c.equals("-") || c.equals("*") || c.equals("/");
    }

    private static int priority(String c) {
        if (c.equals("+") || c.equals("-")) {
            return 0;
        } else if (c.equals("*") || c.equals("/")) {
            return 1;
        } else {
            return -1;
        }
    }
}
